Shortest Paths in Time-varying Networks

Abstract:

Suppose you are given the traffic situation on each road of your city and you want to find the quickest way to your workplace from your home. The city’s road network can be modelled by a graph whose edge weights represent the amount of traffic on the roads. Now the problem boils down to computing a shortest path in this graph, which can be solved by standard algorithms (Dijkstra’s algorithm, Bellman-Ford-Moore algorithm). However, in most practical scenarios, the traffic typically varies with time. So we have a graph whose edge weights are functions of time. We will see that this new setting poses some interesting mathematical questions and computational challenges, some of which have real-world implications.

Video

Need IIIT IDs for access.